package com.example.leetcode.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

/**
 * 给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。
 * 例如：
 * 给定的二叉树是{1,2,3,#,#,4,5}
 * <p>
 * <p>
 * 广度优先遍历bfs
 */
public class Tree7 {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;

        ArrayList<ArrayList<Integer>> print = Print(treeNode1);
        System.out.println(print);
    }


    public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        if (pRoot == null) {
            return new ArrayList<>();
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.add(pRoot);
        while (!deque.isEmpty()) {
            ArrayList<Integer> temp = new ArrayList<>();
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                temp.add(poll.val);
                TreeNode left = poll.left;
                if (left != null) {
                    deque.add(left);
                }
                TreeNode right = poll.right;
                if (right != null) {
                    deque.add(right);
                }
            }
            result.add(temp);
        }

        return result;
    }


}
